package com.hle;

import com.hle.graph.ListGraph;
import java.util.Map;
import java.util.Set;
import com.hle.graph.Graph;
import com.hle.graph.Graph.VertexVisitor;
import com.hle.graph.Graph.WeightManager;
import com.hle.graph.Graph.EdgeInfo;
import com.hle.graph.Graph.PathInfo;

public class Main {

	static WeightManager<Double> mgr = new WeightManager<Double>() {
		@Override
		public int compare(Double w1, Double w2) {
			return w1.compareTo(w2);
		}

		@Override
		public Double add(Double w1, Double w2) {
			return w1 + w2;
		}

		@Override
		public Double zero() {
			// TODO Auto-generated method stub
			return 0.0;
		}
	};


	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//		test1();
		//		testDfs();
		//		testBfs();
		//		testTopological();
//		testMst();
//		testSp();
		testMultSp();
	}
	
	static void testMultSp() {
		Graph<Object, Double> graph = undirectedGraph(Data.SP);
		Map<Object, Map<Object, PathInfo<Object, Double>> > sp = graph.multShortestPath();
		if (sp == null) return;
		sp.forEach((Object v,  Map<Object, PathInfo<Object, Double>> map) -> {
			System.out.println(v + " ------ ");
			map.forEach((Object v1, PathInfo<Object, Double> path) -> {
				System.out.println(v1 + " - " + path);
			});
		});
	}
	
	static void testSp() {
		Graph<Object, Double> graph = undirectedGraph(Data.SP);
		Map<Object, PathInfo<Object, Double>> sp = graph.shortestPath("A");
		if (sp == null) return;
		sp.forEach((Object v, PathInfo<Object, Double> path) -> {
			System.out.println(v + " - " + path);
		});
	}

	static void testMst() {
		Graph<Object, Double> graph = undirectedGraph(Data.MST_01);
		Set<EdgeInfo<Object, Double>> infos = graph.mst();
		for (EdgeInfo<Object, Double> info : infos) {
			System.out.println(info);
		}
	}

	static void testTopological() {
		Graph<Object, Double> graph = directedGraph(Data.TOPO);
		System.out.println(graph.topologicalSort());
	}

	static void testDfs() {
		Graph<Object, Double> graph = directedGraph(Data.DFS_02);
		graph.dfs("a", new VertexVisitor<Object>() {
			@Override
			public boolean visit(Object v) {
				System.out.println(v);
				return v.equals("b");
			}

		});
		System.out.println("---");

		graph.dfs1("a", new VertexVisitor<Object>() {
			@Override
			public boolean visit(Object v) {
				System.out.println(v);
				return v.equals("b");
			}
		});
	}

	static void testBfs() {
		Graph<Object, Double> graph = directedGraph(Data.BFS_02);
		graph.bfs(0, new VertexVisitor<Object>() {
			@Override
			public boolean visit(Object v) {
				System.out.println(v);
				return v.equals(4);
			}
		});
	}


	public static void test1() {
		ListGraph<String, Integer> graph = new ListGraph<>() {
			
		};
		graph.addEdge("v0", "v4", 6);
		graph.addEdge("v1", "v0", 9);
		graph.addEdge("v1", "v2", 3);
		graph.addEdge("v2", "v0", 2);
		graph.addEdge("v2", "v3", 5);
		graph.addEdge("v3", "v4", 1);

		//		graph.bfs("v1");
	}

	/**
	 * 有向图
	 */
	private static Graph<Object, Double> directedGraph(Object[][] data) {
		Graph<Object, Double> graph = new ListGraph<>(mgr) {
		};
		for (Object[] edge : data) {
			if (edge.length == 1) {
				graph.addVerTex(edge[0]);
			} else if (edge.length == 2) {
				graph.addEdge(edge[0], edge[1]);
			} else if (edge.length == 3) {
				double weight = Double.parseDouble(edge[2].toString());
				graph.addEdge(edge[0], edge[1], weight);
			}
		}
		return graph;
	}

	/**
	 * 无向图
	 * @param data
	 * @return
	 */
	private static Graph<Object, Double> undirectedGraph(Object[][] data) {
		Graph<Object, Double> graph = new ListGraph<>(mgr);
		for (Object[] edge : data) {
			if (edge.length == 1) {
				graph.addVerTex(edge[0]);
			} else if (edge.length == 2) {
				graph.addEdge(edge[0], edge[1]);
				graph.addEdge(edge[1], edge[0]);
			} else if (edge.length == 3) {
				double weight = Double.parseDouble(edge[2].toString());
				graph.addEdge(edge[0], edge[1], weight);
				graph.addEdge(edge[1], edge[0], weight);
			}
		}
		return graph;
	}
}
